package LeetCode._01_树;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 
 */
public class _652_寻找重复的子树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private Map<String,Integer> map = new HashMap<>();//存放所有子树的样子以及出现次数
    private List<TreeNode> res = new LinkedList<>(); //存放重复子树的根节点

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverser(root);
        return res;
    }

    //输入一个根节点，然后这个二叉树序列化的样子
    private String traverser(TreeNode root){
        if(root == null){
            return "#";
        }

        //左子树序列化
        String left = traverser(root.left);
        //右子树序列化
        String right = traverser(root.right);

        String subTree = left + "," + right + "," + root.val;

        int cur = map.getOrDefault(subTree,0); //是否在map中，没有就是0
        if(cur == 1){
            res.add(root);
        }
        map.put(subTree,cur+1);
        return subTree;
    }
}
